package ViolenceRecursive;

/**
 * 在 n * n大小的棋盘上摆n个皇后，一共有多少种摆法
 *
 * @author Liaorun
 */
public class NQueens {

    public static void main(String[] args) {
        System.out.println(num1(4));
    }

    public static int num1(int n) {
        if (n < 1) {
            return 0;
        }

        // record[i] -> i行的皇后，放在了第几列上
        int[] record = new int[n];

        return processs1(0, record, n);
    }

    /**
     * @param i      目前来到了第几行，前提：（0..i-1)的皇后，不共行共列或者共斜线
     * @param record 我之前放到棋盘上的皇后，都在record里面
     * @param n      一共有多少行多少列
     * @return 摆完所有的皇后一共有多少种摆法
     */
    private static int processs1(int i, int[] record, int n) {
        // base case
        if (i == n) {
            // 所有的皇后都摆下了，尝试了一种正确的摆法，返回1
            return 1;
        }
        int res = 0;

        // 当前在第i行，遍历尝试在每一列上摆皇后
        for (int column = 0; column < n; column++) {
            // 当前i行的皇后，放在j列，会不会和之前（0..i-1)的皇后，共行共列或者共斜线
            // 是，认为无效
            if (isValid(record, i, column)) {
                record[i] = column;
                res += processs1(i + 1, record, n);
            }
        }
        return res;
    }

    /**
     * 检查新放的一个皇后是否合法
     * 新放的皇后肯定不会共行，但是需要检查是否共列，共斜线这两种情况
     *
     * @param record 已经放了位置的皇后
     * @param i      新放的行
     * @param j      新放的列
     * @return 是否合法
     */
    private static boolean isValid(int[] record, int i, int j) {
        for (int k = 0; k < i; k++) {

            // 新放的皇后肯定不会共行，但是需要检查是否共列，共斜线这两种情况
            // 检查不共列简单，
            // 检查不共斜线：如果新放的皇后的行 - 原来的行 == 新放的皇后的列 - 原来的列
            // 表示两个皇后可以确定一个正方形，唯一对角点，共斜线，否则不共斜线
            if (j == record[k] || Math.abs(j - record[k]) == Math.abs(i - k)) {
                return false;
            }
        }
        return true;
    }

    public static int num2(int n) {
        if (n < 1 || n > 32) {
            return 0;
        }

        // 几皇后问题就在低位放几个1， 32皇后就是 32个1
        int limit = n == 32 ? -1 : (1 << n) - 1;
        return processs2(limit, 0, 0, 0);
    }

    /**
     * @param limit
     * @param colLim      列的限制，1的位置不能放皇后，0的位置可以
     * @param leftDiaLim  左斜线的限制，1的位置不能放皇后，0的位置可以
     * @param rightDiaLim 右斜线的限制，1的位置不能放皇后，0的位置可以
     * @return
     */
    private static int processs2(int limit, int colLim, int leftDiaLim, int rightDiaLim) {
        // base case
        if (colLim == limit) {
            // 所有的皇后都摆下了，尝试了一种正确的摆法，返回1
            return 1;
        }
        int pos = 0;
        int mostRightOne = 0;
        // 得到可以选择尝试的皇后位置
        pos = limit & (~(colLim | leftDiaLim | rightDiaLim));
        int res = 0;
        while (pos != 0) {
            // 获得候选皇后位置最右测的1
            mostRightOne = pos & (~pos + 1);
            // 取过的位置变为0
            pos = pos - mostRightOne;
            res += processs2(limit, colLim | mostRightOne, (leftDiaLim | mostRightOne) << 1, (rightDiaLim | mostRightOne) >>> 1);
        }

        return res;
    }
}
